跳到主要内容

裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity）。是一个关于最大公约数的定理。

其内容是：

设 a,ba,b 是不全为零的整数，对任意整数 x,yx,y，满足 gcd⁡(a,b)∣ax+by\gcd(a,b)\mid ax+by，且存在整数 x,yx,y, 使得 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b).

证明​

对于第一点

由于 gcd⁡(a,b)∣a,gcd⁡(a,b)∣b\gcd(a,b)\mid a,\gcd(a,b)\mid b

所以 gcd⁡(a,b)∣ax,gcd⁡(a,b)∣by\gcd(a,b)\mid ax,\gcd(a,b)\mid by，其中 x,yx,y 均为整数

因此 gcd⁡(a,b)∣ax+by\gcd(a,b)\mid ax+by

对于第二点

  1. 若任何一个等于 00, 则 gcd⁡(a,b)=a\gcd(a,b)=a. 这时定理显然成立。

  2. 若 a,ba,b 不等于 00.

    由于 gcd⁡(a,b)=gcd⁡(a,−b)\gcd(a,b)=\gcd(a,-b),

    不妨设 a,ba,b 都大于 00，a≥b,gcd⁡(a,b)=da\geq b,\gcd(a,b)=d.

    对 ax+by=dax+by=d, 两边同时除以 dd, 可得 a1x+b1y=1a_1x+b_1y=1, 其中 (a1,b1)=1(a_1,b_1)=1.

    转证 a1x+b1y=1a_1x+b_1y=1.

    我们先回顾一下辗转相除法是怎么做的，由 gcd⁡(a,b)→gcd⁡(b,amod  b)→…\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots 我们把模出来的数据叫做 rr 于是，有

    gcd⁡(a1,b1)=gcd⁡(b1,r1)=gcd⁡(r1,r2)=⋯=(rn−1,rn)=1\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1

    把辗转相除法中的运算展开，做成带余数的除法，得

    a1=q1b1+r1(0≤r1<b1)b1=q2r1+r2(0≤r2<r1)r1=q3r2+r3(0≤r3<r2)⋯rn−3=qn−1rn−2+rn−1rn−2=qnrn−1+rnrn−1=qn+1rn\begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned}

    不妨令辗转相除法在除到互质的时候退出则 rn=1r_n=1 所以有（qq 被换成了 xx，为了符合最终形式）

    rn−2=xnrn−1+1r_{n-2}=x_nr_{n-1}+1

    即

    1=rn−2−xnrn−11=r_{n-2}-x_nr_{n-1}

    由倒数第三个式子 rn−1=rn−3−xn−1rn−2r_{n-1}=r_{n-3}-x_{n-1}r_{n-2} 代入上式，得

    1=(1+xnxn−1)rn−2−xnrn−31=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}

    然后用同样的办法用它上面的等式逐个地消去 rn−2,⋯ ,r1r_{n-2},\cdots,r_1,

    可证得 1=a1x+b1y1=a_1x+b_1y. 这样等于是一般式中 d=1d=1 的情况。

推广​

逆定理​

设 a,ba, b 是不全为零的整数，若 d>0d > 0 是 a,ba, b 的公因数，且存在整数 x,yx, y, 使得 ax+by=dax+by=d，则 d=gcd⁡(a,b)d = \gcd(a, b)。

特殊地，设 a,ba, b 是不全为零的整数，若存在整数 x,yx, y, 使得 ax+by=1ax+by=1，则 a,ba, b 互质。

多个整数​

裴蜀定理可以推广到 nn 个整数的情形：设 a1,a2,…,ana_1, a_2, \dots, a_n 是不全为零的整数，则存在整数 x1,x2,…,xnx_1, x_2, \dots, x_n, 使得 a1x1+a2x2+⋯+anxn=gcd⁡(a1,a2,…,an)a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)。其逆定理也成立：设 a1,a2,…,ana_1, a_2, \dots, a_n 是不全为零的整数，d>0d > 0 是 a1,a2,…,ana_1, a_2, \dots, a_n 的公因数，若存在整数 x1,x2,…,xnx_1, x_2, \dots, x_n, 使得 a1x1+a2x2+⋯+anxn=da_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d，则 d=gcd⁡(a1,a2,…,an)d = \gcd(a_1, a_2, \dots, a_n)。

应用​

???+ note "Codeforces Round #290 (Div. 2) D. Fox And Jumping" 给出 nn 张卡片，分别有 lil_i 和 cic_i。在一条无限长的纸带上，你可以选择花 cic_i 的钱来购买卡片 ii，从此以后可以向左或向右跳 lil_i 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 −1-1。

分析该问题，发现想要跳到每一个格子上，必须使得所选数 li1,…,likl_{i_1}, \dots, l_{i_k} 通过数次相加或相减得出的绝对值为 11，也即存在整数 x1,…,xnx_1, \dots, x_n 使得 li1x1+⋯+likxk=1l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1。由多个整数的裴蜀定理逆定理，这相当于从数组 l1,…,lnl_1, \dots, l_n 选择若干个数，满足它们的最大公因数为 1，同时要求代价和最小。

解法 1：我们可以转移思想，因为这些数互质，即为 00 号节点开始，每走一步求 gcd⁡\gcd（节点号，下一个节点），同时记录代价（求边权），就成为了从 00 通过不断 gcd⁡\gcd 最后变为 11 的最小代价。

由于：互质即为最大公因数为 11，gcd⁡(0,x)=x\gcd(0,x)=x 这两个定理，可以证明该算法的正确。选择优先队列优化 Dijkstra 求解。

不过还有个问题，即为需要记录是否已经买过一个卡片，开数组标记由于数据范围达到 10910^9 会超出内存限制，可以想到使用 unordered_map。

解法 2：从数组 l1,…,lnl_1, \dots, l_n 选择若干个数，满足它们的最大公因数为 1，且代价和最小，由此可以想到 0-1 背包问题。

设 fi,jf_{i, j} 表示考虑前 ii 个数且最大公因数为 jj 的最小代价，则有转移方程：

fi,j=min⁡gcd⁡(k,li)=jfi−1,k+ci.f_{i, j} = \min_{\gcd(k, l_i) = j} f_{i - 1, k} + c_i.

DP 后最终的总代价即为 fn,1f_{n, 1}。

如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。而这里 300 个数可达的最大公因数 jj 是很稀疏的，因此还可以使用 unordered_map 代替数组储存下标 jj，优化内存并进一步减少枚举量。

实际上，这里解法 1 建出的图便是解法 2 中动态规划的状态转移图，解法 2 相当于用动态规划求有向无环图的最短路，因此解法 1 和解法 2 是等价的。但解法 2 无需储存全图，同时 DP 的时间复杂度为 O(n+m)O(n + m)，相比 Dijkstra 算法更低，因此解法 2 在时间和空间上更优。

进一步结论​

对自然数 aa、bb 和整数 nn，aa 与 bb 互素，考察不定方程：

ax+by=nax+by=n

其中 xx 和 yy 为自然数。如果方程有解，称 nn 可以被 aa、bb 表示。

记 C=ab−a−bC=ab-a-b。由 aa 与 bb 互素，CC 必然为奇数。则有结论：

对任意的整数 nn，nn 与 C−nC-n 中有且仅有一个可以被表示。

即：可表示的数与不可表示的数在区间 [0,C][0,C] 对称（关于 CC 的一半对称）。00 可被表示，CC 不可被表示；负数不可被表示，大于 CC 的数可被表示。

证明​

由于 aa、bb 互素，因此原方程有整数解。设解为：

{x=x0+bty=y0−at\begin{cases}x=x_0+bt\\y=y_0-at\end{cases}

其中 tt 为整数。取适当的 tt，使得 yy 位于 00 到 a−1a-1 之间。这只需在 y0y_0 上加上或减去若干个 aa，即可得到这样的 tt。

第一步：证明大于 CC 的数都可以被表示。当 nn 大于 CC 时：

ax=n−by>ab−a−b−by⩾ab−a−b−b(a−1)=−aax=n-by>ab-a-b-by\geqslant ab-a-b-b(a-1)=-a

于是 xx 也是非负整数。

第二步：证明 CC 不可被表示，进而 nn 与 C−nC-n 不可能都被表示。

反证法。若 ax+by=ab−a−bax+by=ab-a-b 有非负整数解 xx、yy，则：

ab=a(x+1)+b(y+1)ab=a(x+1)+b(y+1)

由于 aa 与 bb 互素，所以 aa 整除 y+1y+1，bb 整除 x+1x+1，aa 不超过 y+1y+1，bb 不超过 x+1x+1。于是有：

ab=a(x+1)+b(y+1)⩾ab+ab=2abab=a(x+1)+b(y+1)\geqslant ab+ab=2ab

矛盾！第二步证完。

第三步：证明如果 nn 不可被表示，则 C−nC-n 可被表示。

由上可知，若 nn 不可被表示，由于上述方程中已规定 yy 在 00 到 a−1a-1 之间，则 xx 为负。所以：

ab−a−b−ax−by=a(−x−1)+b(a−1−y)ab-a-b-ax-by=a(-x-1)+b(a-1-y)

显然 −x−1-x-1 和 a−1−ya-1-y 均非负，于是 C−nC-n 可被表示。

几何意义​

重新观察方程 ax+by=nax+by=n，将它看成一条直线。直线与两坐标轴在第一象限围成三角形。

当 n<abn<ab 的时候，这个直线在第一象限，至多只能通过一个整点。

根据上述讨论：当 nn 可以被表示的时候，直线恰好经过一个整点；当 nn 不可以被表示的时候，直线不经过整点（在第一象限）。

这结论也可以理解为：作三角形 (0,0)(b,0)(0,a)(0,0)(b,0)(0,a)。随着 nn 从 00 不断增加，直线向右上方平移，整点会一个一个地通过直线，直到最后才撞上两个整点。

因此，小于等于 nn 的能被表示的非负整数的数量，恰好就是直线 ax+by=nax+by=n（含）与两坐标轴（含）在第一象限围成三角形覆盖的整点个数。

另一种解释​

考虑模 bb 意义下每个剩余系中最小能被表示的值是多少——大于他们的可以通过增加若干个 bb 得到。

观察原方程，aa 的若干倍数 0,a,⋯ ,(b−1)a0, a,\cdots, (b−1)a 在 (modb)\pmod b 意义下互不相同。这些数恰好是这些最小值。那么当 n<abn<ab 时，小于等于 nn 的能被表示的非负整数的数量是：

∑i=0[na][n−iab]\sum\limits_{i=0}^{\left[\frac{n}{a}\right]}\left[\frac{n − ia}{b}\right]

这是一个非常经典的直线下整点问题，恰好是这条直线：

y=−abx+nby=-\frac{a}{b}x+\frac{n}{b}

即 ax+by=nax+by=n。

使用类欧几里得算法可以在 O(log⁡max⁡(a,b))O(\log \max(a,b)) 的时间内求解。因此我们得到了计算小于等于 nn 的能被表示的非负整数的数量的工具。

题目​

P3951 NOIP2017 提高组 小凯的疑惑/蓝桥杯 2013 省 买不到的数目